Current airport surface air traffic controllers generally assign surface route paths to aircraft and other vehicles that conform to prescribed routings. Current controllers monitor aircraft positions and movements by observation and by viewing electronic displays where available, and mentally determine surface path assignments based on the predefined routing guidelines for vehicles traversing the airport movement area, normally between runways and ramp entry/exit points. These prescribed routings define direction-of-movement rules along various series of taxiway segments. These routings segregate inbound and outbound surface traffic flows to minimize to the extent possible interference between the flows. However various points of crossing and merging within and between flows are unavoidable, leading to potential crossing and merging conflicts that must be resolved by traffic controllers. Airline ramp traffic controllers assign routings for movement in ramp areas between the airport movement area exit/entry points and terminal gates.
Air traffic controllers issue taxi clearances that typically identify the path to be traversed and a clearance limit in the form of a hold instruction. The hold instruction defines a point along the path towards which the vehicle may move under pilot/operator autonomous control (i.e., pilot discretion) but at which the vehicle must stop unless otherwise directed by the controller. The pilot/operator maintains self-separation with other vehicles to preclude overtaking along the assigned path. In the current system, by defining hold points at crossing or merge intersections on the surface taxiway network of the airport, the traffic controller manages potential conflicts without extensive automation decision-making support. The controller resolves individual potential conflicts as vehicles approach intersections by selecting one of the vehicles for traversal of the intersection and issuing or maintaining holds on the other approaching aircraft.
The use of prescribed routes on the airport surface facilitates surface traffic management, but introduces inherent delay by circumventing more-direct routings between various start and end points for multiple aircraft. Also, the current process of separately resolving individual potential conflicts does not consider network-wide effects, and leads to solutions that are not the best solutions with respect to overall system delays. A more serious concern is the possibility of air traffic controller issued taxi clearances creating surface gridlock. Gridlock is a situation where vehicles are not able to move forward because of oncoming traffic (e.g., two aircraft nose-to-nose on a taxiway segment, four aircraft entering a four-way intersection, a gate or ramp exit blocked by an inbound aircraft, and the like). While current surface traffic controllers readily resolve conflicts among vehicles approaching crossing and merging intersections, the surface traffic controllers can not assure the gridlock-free movement of vehicles on the airport surface on downstream segments. Further, the potential for gridlock is increased during route transition periods where paths are dynamically modified and often partially reversed due to runway configuration changes, which directly impact surface traffic management on the airport surface. Gridlock potential is most problematic at large airports during busy transition periods where numerous alternative routings available to controllers can lead to incompatible path assignments.
Prior art documents that generally address gridlock and vehicle path conflicts are related to various automated systems for railroad network train control. These prior art references apply fixed or moving block control strategies in which the track sections preceding a train are examined for conflicts and trains are prevented from entering a blocked section (i.e., a section occupied by or assigned to a predecessor) using signalization systems. These prior art references allow forward or reverse movement of trains, and allow the use of track sidings as secondary routings to enable one train to pass another on a single track (assigned route). These prior art references include:                U.S. Pat. No. 3,976,272 resolves blockages in part by selecting conflict-free alternative routes if currently available or soon available.        U.S. Pat. No. 4,122,523 in addition enables time window scheduling to resolve conflicts in blocked segments, and further applies a cost-based optimization strategy to minimize system delay.        U.S. Pat. No. 5,623,413 extends these solutions by providing a framework for applying alternative multi-path optimization techniques (e.g., simulated annealing, branch and bound search algorithms) to define schedules that resolve railroad network blockages.        
These prior art references require the availability of routing options or the application of scheduling techniques or both. The capabilities disclosed in these prior art references are not required by the methodology of the present invention herein to resolve conflicts in the airport surface traffic network.
Other related prior art references describe route selection, rescheduling or other network optimization applications. These capabilities are not required by the present invention to generate hold advisories. Some of the other prior art references disclose various means for defining path assignment inputs, these include:                Balakrishnan et al. applies an integer programming formulation for optimizing taxiway operations at an airport, focusing on controlled gate push-backs and taxi reroutes.        Brinton et al. identifies computational solution formulations (e.g., Dijkstra, A* algorithms) that support an automated Surface Movement Management System in determining airport optimal surface routings for arrival and departure aircraft.        Cheng et al. describes the automated Ground-Operation Situation Awareness and Flow Efficiency system to predict aircraft crossing times at selected locations and manipulate airport surface taxi routes and schedules to reduce delays.        García et al. examines the capabilities of a modified minimum-cost maximum flow algorithm and a genetic algorithm to assist air traffic controllers in scheduling and selecting taxi routes to maximize ground airport capacity.        Hatzack et al. designs algorithms to apply job-shop scheduling solutions in the presence of blocking constraints to schedule airport surface traffic movement.        Keith et al. develops a single mixed integer linear programming method to optimize airport taxi routing and runway scheduling.        Nguyen et al. propose an approach to balance optimization objectives to maximize aircraft traffic flow and minimize delay in a generalized air traffic network using a multi-commodity traffic flow integer program.        Rathinam et al. formulates a mixed integer linear program solution for scheduling airport surface taxi movement that accounts for aircraft type and aircraft separation rules.        Wood et al. focuses on the application of scheduling algorithms to integrate airport surface taxiway and runway operations, and demonstrates the application of a dynamic programming departure scheduler with first-come first-serve taxiway heuristics to manage delay.        
Several prior art references also emulate current airport surface traffic control operations which enforce predefined network path direction-of-movement rules to minimize gridlock and manage vehicle crossings of individual vertexes along these predefined paths. For example, Couluris, Mittler et al. describes a method to control aircraft movement through an airport surface link-node network by individually scheduling each aircraft's traversal of a node to resolve conflicts when the aircraft requests entry to that node or a link leading to and connected the that node. Couluris et al. applies predefined network paths to separate inbound and outbound traffic flows.
What is needed is a method for preventing gridlock and resolving potential crossing and merging conflicts among the vehicles on an airport surface area before the conflicts occur that considers simultaneously a multitude of nodes/vertexes that have potentially a multitude of contending vehicles where each vehicle is assigned a path through the surface network.